//
// Created by 下次一定 on 2021/9/21.
//

/*
 * 图中存在负权
 * 1-n 最多经过k条  求最短路径  如果无法到达 输出impossible
 * 换乘问题
 * */


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 51, M = 1000;

int n, m, k;
//backup 上一次迭代的结果
int dist[N], backup[N];

/*a-b的边  权重是 w*/
struct Edge {
    int a, b, w;
} edges[M];

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < k; i++) {
        //将  dist赋值给 backup
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    // 防止负值更新
    if (dist[n] > 0x3f3f3f / 2) return -1;
    else return dist[n];
}

int main() {
    cin >> n >> m >> k;

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    int t = bellman_ford();

    if (t == -1)
        cout << "不存在";
    else cout << t << endl;
}

